package pers.qianyu.month_202012.date_20201222;

import java.util.*;

/**
 * 295. 数据流的中位数
 * https://leetcode-cn.com/problems/find-median-from-data-stream/
 *
 * @author mizzle rain
 * @date 2020年12月22日20:30:17
 */
public class MedianFinder {
    // 后半部分（小顶堆）
    private PriorityQueue<Integer> last = new PriorityQueue<>();
    // 前半部分（大顶堆）
    private PriorityQueue<Integer> pre = new PriorityQueue<>((o1, o2) -> o2 - o1);

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
    }

    public void addNum(int num) {
        if (last.size() < pre.size()) {
            pre.add(num);
            last.add(pre.poll());
        } else {
            last.add(num);
            pre.add(last.poll());
        }
    }

    public double findMedian() {
        if (pre.size() == last.size()) {
            return ((double) (pre.peek() + last.peek())) / 2;
        }
        return pre.size() > last.size() ? pre.peek() : last.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */